/*
快速幂
连接：https://leetcode.cn/problems/powx-n/
题目：Pow(x, n)

简介：递归解题


算法思路：
1. 递归函数的含义：求出 x 的 n 次⽅是多少，然后返回；
2. 函数体：先求出 x 的 n / 2 次⽅是多少，然后根据 n 的奇偶，得出 x 的 n 次⽅是多少；
3. 递归出⼝：当 n 为 0 的时候，返回 1 即可。

*/

class Solution {
public:
    double myPow(double x, int n) {
        if(n>0)
            return pow(x,n);
        else
            return 1/pow(x,-(long long)n);
    }
    double pow(double x,long long n)
    {
        if(n==0)
            return 1;
        double tmp = pow(x,n/2);
        if(n%2==0)
            return tmp*tmp;
        else 
            return tmp*tmp*x;
    }
};

